/**
 * describe:
 *
 * @author chaP
 * @date 2019/01/18
 */
package CodingTest.AC20190118;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个链表，判断链表中是否有环。

 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。



 示例 1：

 输入：head = [3,2,0,-4], pos = 1
 输出：true
 解释：链表中有一个环，其尾部连接到第二个节点。

 */
public class hasCycle {
    class ListNode{
        int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
    }

    /**
     * hash方法
     * @param head
     * @return
     */
    public boolean hasCycle1(ListNode head){
        Set<ListNode> a = new HashSet<>();
        while(head != null){
            if(a.contains(head)){
                return true;
            }
            else{
                a.add(head);
            }
            head = head.next;
        }
        return false;
    }

    /**
     * 快慢指针法,空间复杂度为o（1）
     * @param head
     * @return
     * *思路：
     *1.设置两个指针slow和fast，slow每次走一步，fast每次走两步。如果链表中有环的话，两个指针在里面就形成了
     *一个追击问题，早晚会相遇。
     *2.这里考虑几个问题，如和设计初始时快慢指针的位置
     *3.考虑当没有环时，如果将快指针放到头指针的位置，满指针放到头指针的下一个指针的位置，此时走一次就相遇了，所以
     *不行，因为我们的判断条件就是相遇则有环
     *4.所以，将慢指针放到头指针的位置，快指针放到头指针的下一个指针的位置，因为快指针每次走两步，慢指针每次走一步，
     *快指针先走，如果有环的话，快慢指针一定会相遇，如果没有环的话，则快慢指针永远不会相遇
     */
    public boolean hasCycle2(ListNode head){
        if(head == null || head.next == null)
            return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null){
//            这里做一个判断是因为如果head.next == null,则head.next.next 会报错
            if(slow == fast)
                return true;
            slow = slow.next;
            fast = fast.next;
            if(fast == null)
                return false;
            else
                fast = fast.next;
        }
        return false;

    }
}
